package DP.打家劫舍;

import 其他.DataStructure.TreeNode;
import MyUtils.TreeUtils;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 以后严格 回溯板子:
 *
 *    | (竖)
 *   if
 *   i=
 *  t t t
 * sI sI sI
 *
 */
public class 二叉树型打家劫舍337 {

    Map<TreeNode, Integer> nodeMaxMap = new HashMap<>();
    public int rob(TreeNode root) {
        if(root == null)
            return 0;
        if(root.left==null && root.right==null)
            return root.val;
        return backTrack(root);
    }
    private int backTrack(TreeNode cur) {
        if(cur == null)
            return 0;

        if(nodeMaxMap.containsKey(cur)){
            return nodeMaxMap.get(cur);
        }

        int tou = cur.val
                + (cur.left==null ? 0 : backTrack(cur.left.left) + backTrack(cur.left.right))
                + (cur.right==null ? 0 : backTrack(cur.right.left) + backTrack(cur.right.right));
        int butou = backTrack(cur.left) + backTrack(cur.right); // 这里是+

        nodeMaxMap.put(cur, Math.max(tou, butou));

        return nodeMaxMap.get(cur);// max 只有 最后r 用
    }

    @Test
    public void test() {
        TreeNode root = TreeUtils.strToTree("3,4,5,1,3,null,1");
        System.out.println("RES:" + rob(root));
    }
}
